package com.liyghting.datastructurealgorithm.sort;

/**
 * 如何用快排思想在O(n)查找第K大元素
 * @author LiYiGuang
 * @date 2020/1/13 16:38
 */
public class KthBiggest {
    public static int find(int[] arr, int k) {
        if (arr == null || arr.length < k) return -1;
        return find0(arr, 0, arr.length -1, k);
    }
    private static int find0(int[] arr, int p, int r, int k) {
//        System.out.println("Arrays.toString(arr) = " + Arrays.toString(arr));
//        System.out.println("p = " + p);
//        System.out.println("r = " + r);
        if (p >=r) return arr[arr.length - k];
        int pivot = partition(arr, p, r);
        if (pivot + 1 > k)
            return find0(arr, pivot + 1, r, k);
        else if (pivot + 1 < k )
            return find0(arr, p, pivot - 1, k);
        else
            return arr[pivot];
    }

    /**
     * 获取分区点，并交换
     * @param arr
     * @param p
     * @param r
     * @return
     */
    private static int partition(int[] arr, int p, int r) {
        int pivot = arr[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (arr[j] < pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        arr[r] = arr[i];
        arr[i] = pivot;
//        System.out.println("partition Arrays.toString(arr) = " + Arrays.toString(arr));
//        System.out.println("partition i = " + i);
        return i;
    }

    public static void main(String[] args){
        int[] arr = new int[] { 2,1,1 };
        int data = find(arr, 2);
        System.out.println("data = " + data);
    }
}
